In computer networks, packets of data may be sent from a source to a destination via a network of elements comprising links and nodes according to one or more routing protocols, e.g., link state protocols. Link state protocols generally rely on a routing algorithm resident at each node to construct an optimum (e.g., “best” or “shortest”) route to each available node of the network based on one or more link costs along the path, e.g., using a shortest path first (SPF) algorithm. The results of the SPF are managed by a routing process, and based on these results a forwarding process controls the forwarding of packets appropriately over the shortest route (path).
Generally, data (or “traffic,” e.g., in the form of packets) is forwarded along a single link from a forwarding node to an adjacent (receiving) node based on the SPF algorithm. However, there are certain instances where two or more equal cost best paths are available (e.g., an Equal Cost Multiple Path, or ECMP, as will be understood by those skilled in the art). In these instances, the forwarding node will attempt to implement load-balancing, in which the traffic load is shared equally between the links. That is, assuming two equal cost best paths, the forwarding node may conventionally load-balance the traffic equally (“fairly”) such that each path receives half (1/the number of paths) of the traffic.
Often, however, the equal cost best paths may not be equal paths beyond their equal cost. For instance, other measurements/attributes of the equal cost best paths (e.g., of the links/nodes along the paths) may be different. For example, while the paths may have the same cost to reach the destination, certain nodes/links along the paths may have better (or worse) characteristics that may affect the forwarding of traffic (e.g., an ability to handle the traffic, delays, error rates, etc.). These characteristics may be the result of physical configurations (i.e., “static” configurations, such as link capacity/bandwidth, etc.), or the result of different network conditions (e.g., congestion, delay, etc.) along each path, which may be continuously changing (i.e., are “dynamic”). Current “fair” load-balancing techniques inefficiently address these other measurements/attributes (e.g., by not addressing them at all), thus potentially leading to “unfair” load-balancing among the paths with respect to these other measurements/attributes.